package com.zjsru.oneDay202210;

/**
 * @Author: CookLee
 * @Date: 2022/10/24
 * 给定一个数组 nums ，将其划分为两个连续子数组 left 和 right， 使得：
 *
 * left 中的每个元素都小于或等于 right 中的每个元素。
 * left 和 right 都是非空的。
 * left 的长度要尽可能小。
 *
 * 输入：nums = [5,0,3,8,6]
 * 输出：3
 * 解释：left = [5,0,3]，right = [8,6]
 *
 * 输入：nums = [1,1,1,0,6,12]
 * 输出：4
 * 解释：left = [1,1,1,0]，right = [6,12]
 */
public class PartitionDisjoint {
    /**
     * 求分割点
     * */
    public int partitionDisjoint(int[] nums) {
        int max = nums[0], leftMax = max, idx = 0, len = nums.length;
        for (int i = 1; i < len; i++) {
            //只要发现遍历的数字小于或等于leftMax时，我们就可以通过移动index来划分出新的数组left。
            if (leftMax > nums[i]) {
                //idx既是left数组的位置
                idx = i;
                leftMax = max;
            } else {
                max = Math.max(nums[i], leftMax);
            }
        }
        //idx指向的位置就是数组left的最后一个元素的位置。那么数组left的长度就等于idx + 1了
        return idx + 1;
    }
    
    /**
     * 求分割点解法2
     * 我们可以先通过一次遍历（从后往前）统计出所有后缀的最小值 min，其中 min[i] = x
     * 含义为下标范围在 [i,n−1] 的 nums[i] 的最小值为 x，
     * 然后再通过第二次遍历（从前往后）统计每个前缀的最大值（使用单变量进行维护），找到第一个符合条件的分割点即是答案。
     *
     * */
    public int partitionDisjoint2(int[] nums) {
        int n = nums.length;
        int[] min = new int[n + 10];
        min[n - 1] = nums[n - 1];
        for (int i = n - 2; i >= 0; i--) {
            min[i] = Math.min(min[i + 1], nums[i]);
        }
        for (int i = 0, max = 0; i < n - 1; i++) {
            max = Math.max(max, nums[i]);
            if (max <= min[i + 1]) {
                return i + 1;
            }
        }
        // never
        return -1;
    }
    
    public static void main(String[] args) {
        PartitionDisjoint partitionDisjoint = new PartitionDisjoint();
        int[] nums = new int[] {1, 1, 1, 0, 6, 12};
        System.out.println(partitionDisjoint.partitionDisjoint2(nums));
    }
}
